package com.gxc.tree;

import java.util.Stack;

/**
 * 树的后序遍历
 */
public class Epilogue {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createTree();

        //递归实现后序遍历
        recursion(tree);

        System.out.println("----------");
        Stack<TreeBean> stack = new Stack<>();
        Stack<TreeBean> reverse  = new Stack<>();
        stack.push(tree);
        nonRecursion(stack, reverse);
    }

    /**
     * 非递归实现后序遍历
     * @param stack
     * @param reverse
     */
    private static void nonRecursion(Stack<TreeBean> stack, Stack<TreeBean> reverse) {
        while (!stack.empty()) {
            TreeBean treeBean = stack.pop();
            reverse.push(treeBean);
            if (treeBean.left!=null) stack.push(treeBean.left);
            if (treeBean.right!=null) stack.push(treeBean.right);
        }
        while (!reverse.empty()) {
            TreeBean treeBean = reverse.pop();
            System.out.print(treeBean.value + "  ");
        }
    }

    /**
     * 递归实现后序遍历
     * @param tree
     */
    private static void recursion(TreeBean tree) {
        if (tree == null) return;

        recursion(tree.left);
        recursion(tree.right);
        System.out.print(tree.value + "  ");
    }
}
